//
// Created by 紫霄 on 2020/5/10.
//

#ifndef LEETCODE_33_H
#define LEETCODE_33_H
#include <vector>
using namespace std;
class Solution {
public:
  bool verifyPostorder(vector<int> &postorder) {
    return subTree(postorder, INT_MIN, INT_MAX);
  }
  bool subTree(vector<int> &postorder, int min, int max) {
    if (postorder.empty())
      return true;
    int treeSize = postorder.size();
    if (treeSize == 1) { // 只有一个节点
      return postorder[0] < max && min < postorder[0];
    }
    int treeRoot = postorder[treeSize - 1];
    if (postorder[treeSize - 2] < treeRoot) { //全为左子树
      vector<int> leftTree(postorder.begin(), postorder.end() - 1);
      return subTree(leftTree, min, treeRoot);
    } else if (postorder[treeSize - 2] > treeRoot) {
      auto i = postorder.end() - 2;
      for (; i > postorder.begin() - 1; --i) { // 分离左右子树
        if (*i < treeRoot) {
          ++i;
          vector<int> rightTree(i, postorder.end() - 1);
          vector<int> leftTree(postorder.begin(), i);
          return subTree(rightTree, treeRoot, max) &&
                 subTree(leftTree, min, treeRoot);
        }
      }
      // 说明全为右子树
      vector<int> rightTree(postorder.begin(), postorder.end() - 1);
      return subTree(rightTree, treeRoot, max);
    } else {
      return false;
    }
  }
};
#endif // LEETCODE_33_H
